package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * @author feizns
 * @since 2020/3/9
 */
public class Flatten {

    public void flatten(TreeNode root) {
        helper(root);
    }

    public void flatten2(TreeNode root) {
        if ( root.left != null ) {
            TreeNode leaf = rightLeaf(root.left);
            leaf.right = root.right;
            root.right = root.left;
            root.left = null;
            flatten2(root.right);
        }
    }

    private TreeNode helper(TreeNode node) {
        if ( node != null ) {
            node.right = helper(node.right);
            if ( node.left != null ) {
                TreeNode left = helper(node.left);
                TreeNode leaf = rightLeaf(left);
                node.left = null;
                leaf.right = node.right;
                node.right = left;
            }
        }
        return node;
    }

    private TreeNode rightLeaf(TreeNode node) {
        return node.right != null ? rightLeaf(node.right) : node;
    }

}
